from typing import List


class Solution:
    """
    方法：使用前缀积和后缀积数组
    Args:
        nums: List[int] - 输入整数数组
    Returns:
        List[int] - 返回每个元素除自身外其他元素乘积的数组
    Time: O(n) - 只需遍历数组两次
    Space: O(1) - 只使用常数额外空间（输出数组不计入空间复杂度）
    """
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suf = [1] * n
        for i in range(n-2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]
        pre = 1
        for i, x in enumerate(nums):
            suf[i] *= pre
            pre *= x
        return suf
    
    """
    方法：使用前缀积和后缀积数组分别计算
    Args:
        nums: List[int] - 输入整数数组
    Returns:
        List[int] - 返回每个元素除自身外其他元素乘积的数组
    Time: O(n) - 需要遍历数组两次
    Space: O(n) - 需要两个辅助数组存储前缀积和后缀积
    """
    def productExceptSelf1(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            pre[i] = pre[i -1] * nums[i - 1]
        suf = [1] * n
        for i in range(n-2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]
        return [p * s for p, s in zip(pre, suf)]